Hitherto, VICS (Vehicle Information Communication System) has conducted the service for providing vehicle information indicating a congestion zone and the travel time through FM multiplex broadcasting and beacon for a vehicle navigation system installing a digital map database. The vehicle navigation system receives the vehicle information and displays a colored congestion zone on a map displayed on a screen and calculates the required time to the destination for display.
Thus, to provide the vehicle information, it becomes necessary to pass position information of a road on a digital map. It is also necessary to report the recommended route and the run locus on a digital map to the associated party in the service for receiving the information on the current location and the destination and providing information on the recommended route through which the destination will be reached in the shortest time and a vehicle information collection system (probe information collection system) for collecting locus information, speed information, etc., from a running vehicle (probe car) advanced in study in recent years.
Hitherto, to report the road position on the digital map, generally the link numbers assigned to roads and the node numbers determining nodes such as intersections have been used. However, the node numbers and the link numbers defined in a road network need to be replaced with new numbers with new construction or change of a road and the digital map data produced by each company must also be updated accordingly and thus the system using the node numbers and the link numbers involves an enormous social cost for maintenance.
To improve such a point, JP-A-2003-23357 discloses a method of reporting the road position on the digital map without using the node numbers or the link numbers and in a small data amount.
In this method, sampling points are again set at given intervals in the road zone on the digital map to be reported (called “equal-distance resample”) and compression coding processing is performed for the data string with the position data of the sampling points arranged in order, and the compressed and coded data is transmitted. At the reception party receiving the data, the data string of the position data of the sampling points is reconstructed and the road shape is reproduced on the digital map of the reception party. Using the position data, position determination and position reference are carried out (map matching) on the digital map of the reception party for determining the road zone, as required.
The compression coding for the data string of the position data is performed in the order of (1) conversion of position data to a single variable, (2) conversion of the value represented by the single variable to a value having a statistical bias, and (3) variable-length coding of the provided value as described later:
(1) Conversion of Position Data to a Single Variable
FIG. 26 (a) represents sampling points in a road zone set in equal-distance resample as PJ-1 and PJ. This sampling point (PJ) is uniquely determined by two dimensions of distance (resample length) L from the adjacent sampling point (PJ-1) and angle Θ. Assuming that the distance is constant (L), the sampling point (PJ) can be represented by the single variable of only the angle component Θ from the adjacent sampling point (PJ-1). In FIG. 26 (a), as the angle Θ, the angle Θ based on “absolute azimuth” with the due north azimuth (upper part of the drawing) as 0 degrees and the magnitude specified clockwise in the range of 0 to 360 degrees is shown (absolute azimuth from the due north). When xy coordinates (latitude, longitude) of PJ-1 and PJ are (xj−1, yj−1) and (xj, yj), the angle Θ can be calculated according to the following expression:Θj−1=tan −1{(xj−xj−1)/(yj−yj−1)}
Therefore, the road zone can be represented by the data string of the angle components of the sampling points by indicating the constant distance L between the sampling points and the latitude and longitude of the sampling point as the start or the termination (reference point) separately.
(2) Conversion of a Single Variable Value to a Value Having a Statistical Bias
As shown in FIG. 26 (b), the angle component of each sampling point is represented by the displacement difference from the angle component of the adjacent sampling point, namely, “deflection angle” θj so that the single variable values of the sampling point become statistically biased values suited for variable-length coding. The deflection angle θj is calculated asθj=Θj−Θj−1If the road is linear, the deflection angles θ of the sampling points concentrate on the vicinity of 0 and become data having a statistical bias.
The angle component of the sampling point can be converted into data having a statistical bias by representing the deflection angle θj of an attention sampling point PJ by difference value (predicted difference value or predicted error) Δθj from predicted value Sj of the sampling point PJ predicted using deflection angles θj−1, θj−2, . . . of the preceding sampling points PJ-1, PJ-2, . . . as shown in FIG. 26 (c). The predicted value Sj, for example, can be defined asSj=θj−1or can be defined asSj=(θj−1+θj−2)/2The predicted difference value Δθj is calculated asΔθj=θj−SjIf the road is curved at a constant curvature, the predicted difference values Δθ of the sampling points concentrate on the vicinity of 0 and become data having a statistical bias.
FIG. 26 (d) is a graph to show the data occurrence frequency when a linear road zone is displayed as the deflection angle θ and a curvilinear road zone is displayed as the predicted difference value Δθ. The maximum appears at θ (or Δθ)=0° and the occurrence frequency of θ and Δθ has a statistical bias.
(3) Variable-Length Coding
Next, the data string values converted into values having a statistical bias are variable-length coded. Various types of variable-length coding method such as a fixed numeric value compression method (0 compression, etc.,), a Shannon-Fano code method, a Huffman code method, an arithmetic code method, and a dictionary method exist; any method may be used.
Here, the case where the most general Huffman code method is used will be discussed.
In this variable-length coding, highly frequently occurring data is coded with a small number of bits and less frequently occurring data is coded with a large number of bits for reducing the total data amount. The relationship between the data and code is defined based on a code table.
Now, assume that a list of Δθ at the sampling points of a road zone represented in 1° units is
“0—0—−2—0—0—+1—0—0—−1—0—+5—0—0—0—+1—0”
The case where a code table shown in FIG. 27 combining variable-length coding and run-length coding is used to code the data string will be discussed. The code table defines as follows: Minimum angle resolution (δ) is set to 3° and the representative angle of Δθ in the range of −1° to +1° is 0° and is represented as code “0” and when five successive occurrences of 0° exist, they are represented as code “100” when 10 successive occurrences of 0° exist, they are represented as code “1101.” The code table also defines as follows: The representative angle of Δθ in the range of ±2° to 4° is ±3° and when the value is +, additional bit “0” is added to code “1110” and when the value is −, additional bit “1” is added to code “1110.” The representative angle of Δθ in the range of ±5° to 7° is ±6° and additional bit indicating positive or negative is added to code “111100.” The representative angle of Δθ in the range of ±8° to 10° is ±9° and additional bit indicating positive or negative is added to code “111101.”
Thus, the above-mentioned data string is coded as follows:
“0—0—11101—100—0—0—1111000—100”->“0011101100001111000100”
At the reception party receiving the data, the data string of Δθ is reconstructed using the same code table as that used for coding, and processing opposite to that at the transmission party is performed for reproducing the sampling point position data.
The data is thus coded, whereby the data amount of the coded data can be reduced.
JP-A-2003-23357 mentioned above proposes a method of setting distance L2 of equal-distance resample short in a zone B where the curvature of the road shape is large and setting distance L1 of equal-distance resample long in a linear zone A with a small curvature, as shown in FIG. 28. The reason is that if a largely curved road with a large curvature is resampled at a long distance, it becomes impossible to place a sampling point at a position indicating the characteristic road shape, the reproducibility of the road shape at the reception party worsens, and the possibility that erroneous matching may occur becomes high.
Thus, the value that can be taken by resample length Lj in each zone j (quantization resample length) is preset to, for example, 40/80/160/320/640/1280/2560/5120 meters, Lj is found according to the following expression using curvature radius ρj of the zone j, and the quantization resample length closest to the value is determined the resample length Lj:Lj=ρj·Kr (where Kr is a fixed parameter)
The method disclosed in JP-A-2003-23357 mentioned above was tried using the following three prediction expressions:
Prediction expression 1: Sj=0: Deflection angle is used as it is (substantially prediction is not conducted)
Prediction expression 2: Sj=θj−1: Deflection angle of the preceding node is used
Prediction expression 3: Sj=(θj−1+θj−2)/2: Deflection angle average value of the preceding and preceding preceding nodes is used
Consequently, the compression efficiency of prediction expression 1 was high on average, but to examine the target roads separately, the compression efficiency of prediction expression 2 or 3 was high in some roads.
Specifically, often prediction expression 2 or 3 was suited in roads including a large number of long and gentle curves, such as an express highway; often prediction expression 1 was suited in ordinary roads.
To make a comparison between prediction expressions 2 and 3 of prediction expressions of the same kind, often prediction expression 3 compared a little favorably with prediction expression 2 in compression efficiency.
It is an object of the invention to provide a coded data generation method of efficiently compressing data and generating coded data of a road shape, etc., on a digital map and provide an apparatus for generating the coded data and decoding the coded data.
Patent document 1: JP-A-2003-23357